class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }

    public ListNode(int val,ListNode next) {
        this.val = val;
        this.next = next;
    }
}


public class AddTwoNumbers {
    public static void main(String[] args) {
        //数字895
        //创建链表5->9->8
        ListNode p1 = new ListNode(5);
        ListNode p2 = new ListNode(9);
        ListNode p3 = new ListNode(8);
        p1.next = p2;
        p2.next = p3;

        //数字8732
        //创建链表2->3->7->8;
        ListNode q1 = new ListNode(2);
        ListNode q2 = new ListNode(3);
        ListNode q3 = new ListNode(7);
        ListNode q4 = new ListNode(8);
        q1.next = q2;
        q2.next = q3;
        q3.next = q4;

        //求和895+8732 = 9627
        //链表求和
        ListNode add=addTwoNumbers(p1,q1);
        //反转链表
        ListNode newAdd = reverseList(add);
        while (newAdd != null){
            System.out.print(newAdd.val);
            newAdd = newAdd.next;
        }
    }

    //链表求和
    public static ListNode addTwoNumbers(ListNode head1,ListNode head2) {
        ListNode head = null;
        ListNode cur = null;

        int carry = 0;   //表示相加的jinwei
        for(int sum,val; //声明变量
                head1 !=null || head2 !=null; //循环条件，只要有一条还没走完都继续相加
                head1 = head1 == null ? null : head1.next,
                head2 = head2 == null ? null : head2.next  //每循环一次链表继续往后走
        ){
            sum = (head1 == null ? 0 : head1 .val) +( head2 == null ? 0 : head2 .val) + carry;
            val = sum % 10;
            carry = sum / 10;

            if(head == null) {  //判断是否为首次天机
                head = new ListNode(val);
                cur = head;
            }else {
                cur.next =new ListNode(val);
                cur = cur.next;
            }
        }
        if(carry !=  0) {
            cur.next = new ListNode(1);
        }
        return head;
    }

    //链表反转
    public static ListNode reverseList(ListNode node) {
        ListNode head = null,pre = null;

        while( node !=null ) {
            head = node;
            node = node.next;
            head.next = pre;
            pre = head;
        }
        return head;
    }
}


